Binary Search-iterator

template <typename T> struct Node{
T value;
Node<T>* left=nullptr;
Node<T>* right=nullptr;
Node<T>* parent=nullptr;
BinaryTree<T>* tree=nullptr;
};
// 노드 자체에 대한 정의로 생성
explicit Node(const T& value): value(value) {}
// 자식들에 대한 정의를 통해 생성
Node(const T& value, Node<T>* const left, Node<T>* const right): value(value), left(left), right(right) {
this->left->tree=this->right->tree=tree;
this->left->parent=this->right->parent=this;
}
트리 전체에 대한 포인터를 세팅하기 위한 편의 멤버 함수 set_tree()
template <typename T>
void Node<T>::set_tree(BinaryTree<T>* t){
tree=t;
if(left) left->set_tree(t);
if(right) right->set_tree(t);
}
template <typename T> struct BinaryTree{
Node<T>* root=nullptr;
explicit BinaryTree(Node<T>* const root): root{root} {
root->set_tree(this);
}
};
이진 트리를 위한 반복 자의 탐색 방법
- 전위 탐색(preorder)
항목(잎 노드)를 만나면 바로 리턴
재귀적으로 왼쪽 서브트리를 순회
재귀적으로 오른쪽 서브트리를 순회
template <typename U>
struct PreOrderIterator{
Node<U>* current;
explicit PreOrderIterator(Node<U>* current): current(current) {}
// 반복자 비교를 위한 비교 연산자
bool operator!=(const PreOrderIterator<U>& other){
return current!=other.current;
}
// 역참조를 위한 operator*
Node<U>& operator*(){ return *current; }
// 트리 순회를 위한 operator++
PreOrderIterator<U>& operator++(){
if(current->right){
current=current->right;
while(current->left) current=current->left;
} else {
Node<T>* p=current->parent;
while(p && current == p->right){
current=p;
p=p->parent;
}
current=p;
}
return *this;
}
// 클라이언트를 위한 노출(BinaryTree)
typedef PreOrderIterator<T> iterator;
template <typename T>
iterator BinaryTree<T>::begin(){
Node<T>* n=root;
if(n)
while(n->left) n=n->left;
return iterator{n};
}
template <typename T>
iterator BinaryTree<T>::end(){
return iterator{nullptr};
}
위의 트리 순회를 위한 operator++는 전통적인 재귀함수를 사용하지 않음
// 사용
BinaryTree<string> family{
new Node<string>{"me",
new Node<string>{"mother",
new Node<string>{"mother's mother"},
new Node<string>{"mother's father"}
},
new Node<string>{"father"}
}
};
for(auto it=family.begin(); it!=family.end(); ++it){
cout<<(*it).value<<'\n';
}
전위 순회 클래스
template <typename T>
class BinaryTree<T>::pre_order_traversal{
BinaryTree<T>& tree;
public:
pre_order_traversal(BinaryTree<T>& tree): tree{tree} {}
iterator begin(){ return tree.begin(); }
iterator end(){ return tree.end(); }
} pre_order;
for(const auto& it: family.pre_order){
cout<<it.value<<'\n';
}